package cn.edu.anan.algorithm.sort;

import java.util.ArrayList;

/**
 * 桶排序：
 *  1.思想：
 *      1.1.待排序的数据布相对均匀
 *         （比如给100万用户，按照年龄进行排序，年龄取值范围：0-120）
 *      1.2.首先根据数据取值范围，划分桶，比如把0-10岁、11-20岁、21-30岁...依次分桶
 *      1.3.分桶以后，保证桶之间有序
 *      1.4.在每个桶内，通过快速排序算法，进行排序
 *      1.5.最终按照桶顺序进行访问，得到排好序的数据
 *      1.6.桶排序算法最佳适用场景：
 *          1.6.1.数据分布相对均匀
 *          1.6.2.分桶后，桶之间有顺序保证
 *
 *  2.时间复杂度：
 *      O(n)
 *  3.空间复杂度：
 *      O(n)
 *  4.是否是稳定排序算法：
 *      通过快速排序算法实现，不是稳定排序算法
 */
public class BucketSort {

    /**
     * 排序入口方法
     * @param list
     */
    public static void sort(ArrayList<Integer> list){
        // 如果数据规模小于等于1，则不需要排序
        if(list == null ||
                list.size() <=1){
            return;
        }

        // 将list数据拷贝到数组，方便操作
        Integer[] array = new Integer[list.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }

        // 开始快速排序
        quickSort(array,0,array.length - 1);

        // 清空原list数据，再把排好序的结果数据拷贝回list
        list.clear();
        for (int i = 0; i < array.length; i++) {
            list.add(array[i]);
        }
    }

    /**
     * 快速排序
     * @param array
     * @param low
     * @param high
     */
    public static void quickSort(Integer[] array,int low,int high){
        // 终止条件
        if(low >= high){
            return;
        }

        // 分区函数寻找pivot
        int mid = partition(array,low,high);

        // 低位递归排序
        quickSort(array,low,mid-1);

        // 高位递归排序
        quickSort(array,mid+1,high);
    }

    // 分区函数
    public static int partition(Integer[] a,int low,int high){
        // 选取第一个元素作为pivot（分区点）
        int pivot = a[low];

        // 循环处理low<high
        while (low < high){
            // 从右往左，将小于pivot的数据，放入左边
            while(low < high &&
                    a[high] >= pivot){
                high -= 1;
            }
            a[low] = a[high];

            // 从左往右，将大于pivot的数据，放入右边
            while(low < high &&
                    a[low] <= pivot){
                low += 1;
            }

            a[high] = a[low];

        }

        // 找到分区点
        a[low] = pivot;
        return low;
    }


}
